1. Field of the Invention
The present invention relates to a generalized digital multiplier and a digital filter using said multiplier.
Discussion of Related Art
Digital multipliers are used in digital signal processing, in the calculation of quantities called "scalar products" (or sometimes "internal products") in the form: ##EQU1## In this expression, i designates a rank or order, the terms x.sub.i a group of N variable signals and terms a.sub.i a group of N given coefficients which are constant. Such products are in particular found in digital filtering.
In order to calculate the quantity defined by (1), use is sometimes made of a circuit as shown in FIG. 1. A multiplier 10 receives on a first input 12 successively x.sub.i and on a second input 14 successively a.sub.i. At its output 16, the multiplier successively supplies the products a.sub.i x.sub.i. An accumulator 18 has first and second inputs 20, 24 and an output 22 looped onto the second input 24. After N clock strokes (if i assumes all the integral values between 0 and N-1), the accumulator supplies the sought product P.
Another way of carrying out this operation consists of using a procedure called "distributed arithmetic". It firstly consists of breaking down the terms x.sub.i into their B bits: ##EQU2## in which j ranges between 0 (lowest order bit) and B-1 (highest order bit). This, shown in equation 1, involves a double summation: ##EQU3## In this operation, it is possible to reverse the order of the summations and write: ##EQU4## As the bits x.sub.ij can assume the value 0 or 1, each product a.sub.i x.sub.ij 2.sup.j, for j given, is equal either to 0 or to a.sub.i 2.sup.j. The sum f.sub.j of N such products is the sum of N terms, whereof each can assume two values. Therefore this sum can assume 2.sup.N different values. All these 2.sup.N values are determined and can be calculated beforehand because the a.sub.i are themselves determined and known.
Thus, the bracketed term in equation (3) is equal to one of the terms of this group of values and which is defined by the N bits x.sub.ij, in which the order j is fixed and the order i varies from 0 to N-1.
A multiplier for performing this procedure is in the form shown in FIG. 2. Shift registers R.sub.0, R.sub.1, R.sub.i, R.sub.N-1 with B cells, each contain the B bits of each word x.sub.i. A read only memory or ROM 30 of two words of m bits has N Inputs E.sub.1, E.sub.2 . . . , E.sub.i . . . , E.sub.N-1 connected to the respective outputs of the N registers R.sub.i. In said memory are placed the 2.sup.N possible values referred to hereinbefore for the partial products. Memory 30 has an output S connected to an adder-accumulator 34 with a first input 35, an output 36 and a second input 37. Output 36 is relooped onto the second input 37. A not shown clock times the shifting in the registers, the reading of the memory and the adder-subtractor.
When after a clock stroke a group of N bits x.sub.ij (j determined, i between 0 and N-1) is applied to the memory inputs E.sub.1. . . , E.sub.N-1, the memory is addressed by this group and supplies the corresponding product f.sub.j. It is then necessary to form the sum of these partial products, which is carried out by adder 34.
For simplification purposes, it is assumed hereinbefore that all the products to be added were positive, i.e. that only additions had to be carried out. However, in practice the considered numbers have a sign. Therefore the supplementary question arises as to the sign of the various manipulated quantities. However, the Expert knows how to solve this question (use of the two's complement binary code) and it is consequently unnecessary to go into detail about this here.
Another method for obtaining a scalar product is the use of a so-called "parallel multiplier" circuit. On having to multiply a term a by a term x to obtain the partial product Pr, as stated hereinbefore for (3), it is possible to break down x into its bits: ##EQU5## The product ax is consequently in the form: ##EQU6## The term X.sub.j is a bit equal to 0 or 1. The term a2.sup.j is a word shifted by j positions.
Thus, in material terms, the expression (4) represents the addition to the partial result obtained before order j of a word a shifted by j positions, conditionally with respect to the value of bit A.sub.j of order j of the binary representation of term a: ##EQU7## The general diagram of a parallel multiplier for 4 bit words (which corresponds in the present notation to N=4) is shown in FIG. 3. It comprises four adders Ad.sub.0, Ad.sub.1, Ad.sub.2 and Ad.sub.3, each constituted by four cells, whose structure is given in FIG. 4. A cell C comprises a first input 40 receiving a first bit, a second input 42 receiving a second bit, a hold input 44, a hold output 46, a propagation input 48 and a propagation output 50.
The four cells of the first adder Ad.sub.0 respectively form the products A.sub.0 X.sub.0, A.sub.1 X.sub.0, A.sub.2 X.sub.0 and A.sub.3 X.sub.0.
Adder Ad.sub.1 is shifted by one position to the left compared with adder Ad.sub.0. Its four cells perform the operation consisting of adding to the results supplied by the four cells of adder Ad.sub.0, the word a (A.sub.3 A.sub.2 A.sub.1 A.sub.0) shifted by one position to the left.
Finally, the multiplier has eight outputs P.sub.0 to P.sub.7 on which is found the result of the product of a by x.
Each adder of the multiplier of FIG. 3 can be diagrammatically represented in the manner shown in FIG. 5. A conditional adder Ad.sub.i comprises an input E.sub.i receiving a word to which is added the word a conditionally to the value of bit X.sub.i and supplies the result on output S.sub.i.
The block diagram of a parallel multiplier is consequently that of FIG. 6 with B conditional adders Ad.sub.0, Ad.sub.1 . . . Ad.sub.B-1.
In practice, as a is known, it is a question of carrying out an addition, whereof one of the operands (a) is known. This constant is broken down into bits (A.sub.0, A.sub.1 . . . A.sub.B-1) equal to 0 or 1, as a function of a known distribution. Thus, in advance, it is possible to produce specialized adders for each constant. For this purpose, it is merely necessary to adapt a conventional cell, like that of FIG. 4, in order to specialize it for the addition of a bit equal to 0 or 1. Therefore the complexity of the circuit is reduced by a factor almost equal to 2.
French patent application No. 86.13222 filed on Sept. 22 1986 describes two specialized addition cells of this type. This is illustrated by the attached FIGS. 7a and 7b. The addition cell of FIG. 7a comprises a data input x.sub.i receiving a bit, an inverter 50, a hold input C.sub.i, a switch 52 constituted by a P channel CMOS transistor 53 and a N channel CMOS transistor 55, an excusive OR gate 56 having an output S.sub.i, a N channel CMOS transistor 58 receiving a fixed potential V.sub.SS corresponding to logic state 1 and supplying a hold output signal C.sub.i+1. Transistors 53 and 55 respectively receive on their gates the bits X.sub.i and X.sub.i. Transistor 58 is controlled by the complement A.sub.i of bit A.sub.i.
The cell of FIG. 7b comprises the same elements, except that transistors 53 and 55 no longer receive X.sub.i and X.sub.i and instead receive X.sub.i and X.sub.i and that the P channel CMOS transistor 59 receives a fixed potential V.sub.dd corresponding to logic state 0.
The addition cells of FIGS. 7a and 7b are shown in the form of logic gates in FIGS. 8a and 8b. The addition cell of FIG. 8a is thus reduced to two logic gates, namely an exclusive OR gate 60 and an AND gate 62. Each gate receives on one input the bit X.sub.i and on the other input the hold bit C.sub.i. The AND gate 62 supplies the hold bit C.sub.i+1 and the exclusive OR gate 60 the sum bit S.sub.i.
The addition cell shown in FIG. 8b comprises an inverter 63, an exclusive OR gate 60 and an OR gate 64. Inverter 63 receives bit X.sub.i. Its output is connected to one of the inputs of the exclusive OR gate 60, whilst the other input receives the hold bit C.sub.i. The output of the exclusive OR gate 60 supplies the sum S.sub.i. Finally, OR gate 54 receives on its inputs bits X.sub.i and C.sub.i and supplies the hold bit C.sub.i+1.
Thus, a complete adder comprises addition cells like those shown in FIGS. 7a and 7b or 8a and 8b. These addition cells are connected in series, i.e. the hold output of one addition cell is connected to the hold input of the following addition cell.
FIG. 9 diagrammatically shows an adder of this type. It comprises a group of addition cells CA.sub.0, CA.sub.1, CA.sub.j, CA.sub.B-1, which are connected in series. Each addition cell receives a bit X.sub.j and has a specific structure, which is a function of the logic value of the bit A.sub.j of the fixed and known operand A.sub.B-1, . . . A.sub.1, A.sub.0.
In order to obtain an operational adder from said adder, it is necessary to add a multiplexer as shown in FIG. 10. In the latter, the conditional adder of order i, i.e. AdC.sub.i is constituted by an adder Ad.sub.i according to FIG. 9 and receives a partial sum S.sub.i from a multiplexer MX.sub.i having two inputs, one input e.sub.i being connected to the output of adder Ad.sub.i and the other e'.sub.i to the input of said same adder. This multiplexer has a control input ec.sub.i, which receives the bit X.sub.i, which is a conditional bit, as well as an output s.sub.i, which supplies a new sum S.sub.i+1. If the conditional bit X.sub.i is at 0, the multiplexer directly supplies S.sub.i "short-circuiting" adder Ad.sub.i, so that we obtain S.sub.i+1 -S.sub.i. If the conditional bit X.sub.i is at 1, the addition carried out in Ad.sub.i is taken into account and a new sum S.sub.i+1 differing from S.sub.i is obtained (S.sub.i+1 -S.sub.i +a.sub.i).
Such an adder can be used no matter what the sign of the two operands. In the case where the fixed operand is negative, it is merely necessary to choose the addition cells in such a way that this operand is represented in two's complement code.
The adder can also be used as a subtractor, it being sufficient in this case to interchange the addition cells of the first and second type which, as in the preceding case, amounts to adding the complement of the fixed operand and to wire the hold bit C.sub.0 to the logic value 1, which amounts to adding the fixed operand -B to the variable operand A.
A parallel multiplier, like that shown in FIG. 6, constituted by adders like that of FIG. 10 treating a fixed operand, therefore makes it possible to obtain a product of type ax. In order to obtain a quantity of form: ##EQU8## it is necessary to have a plurality of N multipliers of this type, each dedicated to one of the fixed operands a.sub.0 . . . a.sub.N-1 and each receiving the N terms X.sub.0 . . . X.sub.N-1. A final adder will give the scalar product P.
Although satisfactory in certain respects, these devices, no matter whether they are based on distributed arithmetic or parallel multipliers with a fixed operand, are complex and difficult to realize. Thus, although distributed arithmetic is well adapted when the length of the scalar products is limited (typically below 10) it becomes problematical beyond this, because the size of the memory increases exponentially with the length. For great lengths it is necessary to subdivide the memory into several submemories, whose partial results must then be summated. With regards the integrated circuit performing the operation, this will lead to a loss of a considerable part of the regularity of the etching design. As regards the solution with parallel multipliers, the control of the arrival of the different coefficients is difficult and the connections between the elements have prohibitive lengths on the integrated circuit.